from typing import List


class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:

        c = {}

        def find(x):
            if x not in c:
                c[x] = x
                return x
            if c[x] == x:
                return x
            else:
                c[x] = find(c[x])
                return c[x]

        def merge(i, j):
            x = find(i)
            y = find(j)
            c[x] = y

        for equality in equations:
            if equality[1] == "=":
                # 相同的放在一起
                merge(equality[0], equality[3])

        for equality in equations:
            if equality[1] == "!":
                x = find(equality[0])
                y = find(equality[3])
                if x == y:
                    return False
        return True


if __name__ == "__main__":
    Solution().equationsPossible(["a==b", "a!=b"])
